package com.github.hgkmail.hello.leetcode101.base;

//并查集->父坐标数组
//并查集class简单实现：父坐标数组(一维)、初始化、find root、is connected、union（5点）
public class UF {
    //父坐标数组(一维)
    public int[] parent;
    //初始化
    public UF(int len) {
        parent = new int[len];
        for (int i = 0; i < len; i++) {
            parent[i]=i; //指向自己
        }
    }
    //迭代查找根坐标(推荐，够简洁)
    public int find(int i) {
        while (parent[i]!=i) {
            i=parent[i];
        }
        return i;
    }
    //是否相连（根坐标是否相同）
    //可用于判断无向图是否有环：将一条边加入UF前，判断2个节点是否相连，如果相连，那么加入这条边后必定成环
    public boolean isConnected(int i, int j) {
        return find(i)==find(j);
    }
    //合并
    public void union(int i, int j) {
        int rootI=find(i);
        int rootJ=find(j);
        if (rootI==rootJ) {
            return;
        }
        parent[rootI]=rootJ; //把左边挂在右边下面
    }

    //测试
    public static void main(String[] args) {
        UF uf = new UF(5);
        uf.union(0,1); //分量1
        uf.union(2,3); //分量2
        System.out.println(uf.isConnected(0,2));
        uf.union(1,4);
        uf.union(3,4);
        System.out.println(uf.isConnected(0,2));
    }
}
